package ua.mykola.ds.list;

/**
 * A doubly linked list, the right pointers are point to the next node, the left pointers are point randomly. How do a deep duplication of this linked list
 * structure.
 */
public class LinkedListWithRandomCopier
{

    public NodeWithRandom deepClone(NodeWithRandom inputHead)
    {
        NodeWithRandom nextold = inputHead;

        // oldNode0>newNode0>oldNode1>odlNode1...>oldNodeN>oldNodeN
        while (nextold != null)
        {
            NodeWithRandom newNode = new NodeWithRandom(nextold.name);
            newNode.next = nextold.next;
            nextold.next = newNode;
            nextold = nextold.next.next;
        }

        // random
        nextold = inputHead;
        while (nextold != null)
        {
            nextold.next.random = nextold.random.next;
            nextold = nextold.next.next;
        }

        // deinterleave
        NodeWithRandom newRoot = inputHead.next;
        nextold = inputHead;
        while (nextold.next.next != null)
        {
            // old
            nextold.next = nextold.next.next;
            // new
            nextold.next.next = nextold.next.next.next;
            nextold = nextold.next.next;
        }
        nextold.next = null;

        return newRoot;
    }

}
